package cn.jdemo.algorithm.sort;

import java.util.Arrays;

public class Temp {

    static int[] tmp;
    public static void main(String[] args) {
        int[] arrs = new int[]{6,5,4,9,10,3,1,2,0};
        tmp = new int[arrs.length];
        System.out.println("sort before:"+Arrays.toString(arrs));
        mergeSort(arrs,0,arrs.length-1);
        System.out.println("sort after:"+Arrays.toString(arrs));
    }

    private static void mergeSort(int[] arrs, int left, int right) {
        if(left >= right){
            return;
        }
        int mid = ((right-left)>>1) + left;
        mergeSort(arrs,left,mid);
        mergeSort(arrs,mid+1,right);
        merge(arrs,left,mid,right);
    }

    private static void merge(int[] arrs, int left, int mid, int right) {
        for (int i = left; i <=right; i++) {
            tmp[i] = arrs[i];
        }

        int j = left;
        int k = mid+1;
        for (int i = left; i <= right; i++) {
            if(j == mid+1){
                arrs[i] = tmp[k++];
            }else if(k == right+1){
                arrs[i] = tmp[j++];
            }else if (tmp[j] <= tmp[k]){
                arrs[i] = tmp[j++];
            }else{
                arrs[i] = tmp[k++];
            }
        }

    }

    private static void swap(int[] arrs,int x, int y) {
        if (x == y){
            return;
        }
        arrs[x] = arrs[x] ^ arrs[y];
        arrs[y] = arrs[x] ^ arrs[y];
        arrs[x] = arrs[x] ^ arrs[y];
    }

}
